/*
 * @lc app=leetcode.cn id=847 lang=typescript
 *
 * [847] 访问所有节点的最短路径
 */

// @lc code=start
function shortestPathLength(graph: number[][]): number {
  const m = graph.length;
  // 队列，保存格式[节点，mask，dist]
  // mask是二进制格式，每位表示一个节点，值为1的话表示访问过了
  const queue: [number, number, number][] = [];
  // 保存当前节点下mask状态是否被访问过
  const visited = new Array(m).fill(0).map((_) => new Array(1 << m).fill(0));
  // 初始化队列数据
  for (let i = 0; i < m; i++) {
    let mask = 1 << i;
    queue.push([i, mask, 0]);
    visited[i][mask] = 1;
  }

  // bfs
  while (queue.length) {
    const [u, mask, dist] = queue.shift();
    // 如果mask位数都是1的话，表示u开始的位置，已经访问完所有的节点。返回dist
    if (mask === (1 << m) - 1) {
      return dist;
    }
    // 扩展当前节点的状态
    for (const v of graph[u]) {
      const next = mask | (1 << v);
      if (!visited[v][next]) {
        queue.push([v, next, dist + 1]);
        visited[v][next] = 1;
      }
    }
  }
}
// @lc code=end
